package trees;

import beans.TreeNode;

import java.util.LinkedList;

/**
 * @author pengfei.hpf
 * @date 2020/3/30
 * @verdion 1.0.0
 */
public class BSTIterator {
    LinkedList<TreeNode> list;
    public BSTIterator(TreeNode root) {
        list = new LinkedList<>();
        build(root);
    }

    private void build(TreeNode root){
        if(root == null){
            return;
        }
        list.add(0,root);
        build(root.left);
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = list.removeFirst();
        if(node != null && node.right != null){
            //TODO: 注意右节点处理
            build(node.right);
        }
        return node.val;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return list.size() != 0;
    }
}
